package commonfunctions;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Stack;

import user.data.Data;

public class Functions {
	
	public static ArrayList<ArrayList<Integer>> trackLists(Matrix tracks)
	{
		ArrayList<ArrayList<Integer>> toReturn = new ArrayList<ArrayList<Integer>>();
		
		ArrayList<Integer> added = new ArrayList<Integer>();
		
		for (int i = 0; i < tracks.length(); i++)
		{
			if (!added.contains(i))
			{
				ArrayList<Integer> toCheck = new ArrayList<Integer>();
				toCheck.add(i);
				ArrayList<Integer> thisTrack = new ArrayList<Integer>();
				while (toCheck.size() > 0)
				{
					int thisItem = toCheck.remove(0);
					for (int j = 0; j < tracks.length(); j++)
					{
						if (!toCheck.contains(j) && !thisTrack.contains(j) && !added.contains(j) && (tracks.getBoolean(thisItem, j) || tracks.getBoolean(j, thisItem)))
							toCheck.add(j);
					}
					thisTrack.add(thisItem);
				}
				added.addAll(thisTrack);
				toReturn.add(thisTrack);
			}
		}
		
		return toReturn;
	}

	/**
	 * returns the index of the next item in the path, or -1 if it's the end of a path.
	 * 
	 * @param paths
	 * @return
	 */
	public static int nextInPath(boolean[] paths)
	{
		for (int k = 0; k < paths.length; k++)
		{
			if (paths[k])
				return k;
		}
		return -1;
	}

	/**
	 * returns the list of indices of observations that are the start points of a path
	 * 
	 * @param prunedGraph
	 * @return
	 */
	public static ArrayList<Integer> trackStarts(Matrix prunedGraph)
	{
		ArrayList<Integer> toReturn = new ArrayList<Integer>();
		ArrayList<ArrayList<Integer>> tracks = trackLists(prunedGraph);
		
		for (int i = 0; i < tracks.size(); i++)
		{
			int min = prunedGraph.length();
			for (int j = 0; j < tracks.get(i).size(); j++)
			{
				if (tracks.get(i).get(j) < min)
					min = tracks.get(i).get(j);
			}
			toReturn.add(min);
		}
		
		return toReturn;
	}
	/**
	 * returns the list of indices of observations that are the start points of a path
	 * 
	 * @param prunedGraph
	 * @return
	 */
	public static ArrayList<Integer> trackEnds(Matrix prunedGraph)
	{
		ArrayList<Integer> toReturn = new ArrayList<Integer>();
		ArrayList<ArrayList<Integer>> tracks = trackLists(prunedGraph);
		
		for (int i = 0; i < tracks.size(); i++)
		{
			int max = 0;
			for (int j = 0; j < tracks.get(i).size(); j++)
			{
				if (tracks.get(i).get(j) > max)
					max = tracks.get(i).get(j);
			}
			toReturn.add(max);
		}
		
		return toReturn;
	}
	
	/**
	 * This function takes a graph and assigns a "time" mapping to each node. Useful for the Hungarian
	 * algorithm, especially when we can't depend on frame numbers.
	 * 
	 * @param weights
	 * @return
	 */
	public static int[] getTimeMappings(Matrix weights)
	{
		ArrayList<ArrayList<Integer>> groupings = new ArrayList<ArrayList<Integer>>();
		ArrayList<ArrayList<Double>> maxWeightsFromTo = new ArrayList<ArrayList<Double>>();
		for (int i = 0; i < weights.length(); i++)
		{
			groupings.add(new ArrayList<Integer>());
			groupings.get(i).add(i);
			maxWeightsFromTo.add(new ArrayList<Double>());
			for (int j = 0; j < weights.length(); j++)
			{
				if (weights.get(i, j) != 0.0)
					maxWeightsFromTo.get(i).add(weights.get(i, j));
				else
					maxWeightsFromTo.get(i).add(weights.get(j, i));
			}
		}
		ArrayList<Point> negativeWeights = new ArrayList<Point>();
		for (int i = 0; i < weights.length(); i++)
		{
			for (int j = 0; j < weights.length(); j++)
			{
				if (weights.get(i, j) <= -0.5 * Math.abs(Data.DOMINANT_VALUE))
				{
					negativeWeights.add(new Point(i, j));
				}
			}
		}
		
		while (negativeWeights.size() > 0)
		{
			for (int i = 0; i < negativeWeights.size(); i++)
			{
				if (maxWeightsFromTo.get(negativeWeights.get(i).x).get(negativeWeights.get(i).y) < 0.0)
				{
					int firstNode = Math.min(negativeWeights.get(i).x, negativeWeights.get(i).y);
					int secondNode = Math.max(negativeWeights.get(i).x, negativeWeights.get(i).y);
					groupings.get(firstNode).addAll(groupings.remove(secondNode));
					maxWeightsFromTo.remove(secondNode);
					for (int j = 0; j < maxWeightsFromTo.size(); j++)
					{
						double value = Math.max(maxWeightsFromTo.get(j).get(firstNode), 
												maxWeightsFromTo.get(j).remove(secondNode));
						maxWeightsFromTo.get(j).set(firstNode, value);
					}
					for (int j = 0; j < negativeWeights.size(); j++)
					{
						if (negativeWeights.get(j).x == secondNode)
							negativeWeights.set(j, new Point(firstNode, negativeWeights.get(j).y));
						if (negativeWeights.get(j).x > secondNode)
							negativeWeights.set(j, new Point(negativeWeights.get(j).x - 1, 
															 negativeWeights.get(j).y));
						if (negativeWeights.get(j).y == secondNode)
							negativeWeights.set(j, new Point(negativeWeights.get(j).x, firstNode));
						if (negativeWeights.get(j).y > secondNode)
							negativeWeights.set(j, new Point(negativeWeights.get(j).x, 
															 negativeWeights.get(j).y - 1));
					}
				}
			}
			
			negativeWeights = new ArrayList<Point>();
			for (int i = 0; i < maxWeightsFromTo.size(); i++)
			{
				for (int j = 0; j < maxWeightsFromTo.get(i).size(); j++)
				{
					if (maxWeightsFromTo.get(i).get(j) <= -0.5 * Math.abs(Data.DOMINANT_VALUE))
					{
						negativeWeights.add(new Point(i, j));
					}
				}
			}
		}
		ArrayList<ArrayList<Integer>> orderedGroupings = new ArrayList<ArrayList<Integer>>();
		while (groupings.size() > 0)
		{
			int minGrouping = 0;
			for (int i = 0; i < groupings.size(); i++)
			{
				if (groupings.get(minGrouping).get(0) > groupings.get(i).get(0))
					minGrouping = i;
			}
			orderedGroupings.add(groupings.remove(minGrouping));
		}
		int[] toReturn = new int[weights.length()];
		
		for (int i = 0; i < orderedGroupings.size(); i++)
		{
			for (int j = 0; j < orderedGroupings.get(i).size(); j++)
			{
				toReturn[orderedGroupings.get(i).get(j)] = i;
			}
		}
		
		return toReturn;
	}
	
	public static double getPathSums(Matrix weights, Matrix tracks)
	{
		double toReturn = 0.0;
		
		ArrayList<Integer> seenNodes = new ArrayList<Integer>();
		ArrayList<ArrayList<Integer>> nodeTracks = new ArrayList<ArrayList<Integer>>();
		
		for (int i = 0; i < weights.length(); i++)
		{
			ArrayList<Integer> thisTrack = new ArrayList<Integer>();
			Stack<Integer> nodesToCheck = new Stack<Integer>();
			if (!seenNodes.contains(i))
				nodesToCheck.push(i);
			while (!nodesToCheck.empty())
			{
				int thisNode = nodesToCheck.pop();
				if (!seenNodes.contains(thisNode))
				{
					seenNodes.add(thisNode);
					thisTrack.add(thisNode);
					for (int j = 0; j < weights.length(); j++)
					{
						if(tracks.getBoolean(thisNode, j) || tracks.getBoolean(j, thisNode))
							nodesToCheck.add(j);
					}
				}
			}
			nodeTracks.add(thisTrack);
		}
		
		for (int i = 0; i < nodeTracks.size(); i++)
		{
			for (int j = 0; j < nodeTracks.get(i).size(); j++)
			{
				for (int k = j + 1; k < nodeTracks.get(i).size(); k++)
					toReturn += weights.get(nodeTracks.get(i).get(j), nodeTracks.get(i).get(k));
			}
		}
		
		return toReturn;
	}
}
